package bin_tree.seachtree;

import java.util.NoSuchElementException;

/**
 * 基于整型
 * 普通的二分搜索树
 *
 * @author 是阿秋啊
 * @date 2022/03/21 13:52
 **/
public class BST {
    private class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    private int size;
    private TreeNode root;

    //添加操作
    public void add(int val) {
        root = add(root, val);
    }

    //查找元素val是否存在
    public boolean contains(int val) {
        return contains(root, val);
    }

    //找到BST中的最小值
    public int findMin() {
        if (size == 0) {
            throw new NoSuchElementException("BST is empty! cannot find min");
        }
        TreeNode minNode = minNode(root);
        return minNode.val;
    }

    //找到BST中的最大值
    public int findMax() {
        if (size == 0) {
            throw new NoSuchElementException("BST is empty! cannot find max");
        }
        TreeNode maxNode = maxNode(root);
        return maxNode.val;
    }

    //删除最小值节点，并返回最小值
    public int removeMin() {
        int min = findMin();
        root = removeMin(root);
        return min;
    }

    //删除最大值节点，并返回最大值
    public int removeMax() {
        int max = findMax();
        root = removeMax(root);
        return max;
    }

    //删除值为val的任意节点
    public void remove(int val) {
        root = remove(root, val);
    }

    //修改值为val的节点值变为newVal
    public void set(int val,int newVal) {
        remove(val);
        add(newVal);
    }
    /**
     * 删除以root为根节点中值为val的节点
     *
     * @param root
     * @param val
     * @return
     */
    private TreeNode remove(TreeNode root, int val) {
        if (root == null) {
            // 把树中所有节点都遍历完还没找到值为val的节点，就不存在值val的节点
            throw new NoSuchElementException("BST中没有值为" + val + " 的节点。");
        } else if (val > root.val) {
            // 此时待删除的节点位于左子树
            root.right = remove(root.right,val);
            return root;
        } else if (val < root.val) {
            // 此时待删除的节点位于右子树
            root.left = remove(root.left,val);
            return root;
        } else {
            // 此时root.val == val
            // root就是待删除的节点
            if (root.left == null) {
                //只有有右孩子
                TreeNode right = root.right;
                root.right = root = null;
                size--;
                return right;
            }
            if (root.right == null) {
                //只有左孩子
                TreeNode left = root.left;
                root.left = root = null;
                size--;
                return left;
            }
            // 此时说明root.left 和 root.right 都不为空
            // Hibbard Deletion
            // 方法一：找到后继节点
            TreeNode successor = minNode(root.right);
            // removeMin中size已经--
            // 1.先让后继节点的右树连接root删除右树最小节点后的右树
            successor.right = removeMin(root.right);
            // 2.再让后继节点的左树连接root的左树
            // 1和2顺序不可颠倒
            successor.left = root.left;
            // 删除root节点
            root.left = root.right = root = null;
            // 拼接后继节点
            return successor;
            //方法二：找到前驱节点
//            TreeNode prevNode = maxNode(root.left);
//            prevNode.left = removeMax(root.left);
//            prevNode.right = root.right;
//            root.left = root.right = root = null;
//            return prevNode;
        }
    }

    /**
     * 删除以root为根的最大值节点
     *
     * @param root
     * @return
     */
    private TreeNode removeMax(TreeNode root) {
        if (root.right == null) {
            TreeNode left = root.left;
            root.left = root = null;
            size--;
            return left;
        }
        root.right = removeMax(root.right);
        return root;
    }

    /**
     * 删除以root为根的最小值节点
     *
     * @param root
     * @return
     */
    private TreeNode removeMin(TreeNode root) {
        if (root.left == null) {
            TreeNode right = root.right;
            root.right = root = null;
            size--;
            return right;
        }
        root.left = removeMin(root.left);
        return root;
    }

    /**
     * 找到以root为根节点的BST中的最大节点
     *
     * @param root
     * @return
     */
    private TreeNode maxNode(TreeNode root) {
        if (root.right == null) {
            //此时root为最大值
            return root;
        }
        //不断向右树中递归
        return maxNode(root.right);
    }

    /**
     * 找到以root为根节点的BST中的最小节点
     *
     * @param root
     * @return
     */
    private TreeNode minNode(TreeNode root) {
        if (root.left == null) {
            //此时root为最小值
            return root;
        }
        //不断向左树中递归
        return minNode(root.left);
    }

    /**
     * 判断当前以root为根的BST中是否包含了val
     *
     * @param root
     * @param val
     * @return
     */
    private boolean contains(TreeNode root, int val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        } else if (val > root.val) {
            return contains(root.right, val);
        } else {
            return contains(root.left, val);
        }
    }

    /**
     * 向以root为根的BST中插入一个新的节点val
     *
     * @param root
     * @param val
     * @return
     */
    private TreeNode add(TreeNode root, int val) {
        TreeNode newNode = new TreeNode(val);
        if (root == null) {
            size++;
            return newNode;
        }
        if (val < root.val) {
            //左树中插入
            root.left = add(root.left, val);
        }
        //不允许等于的情况
        if (val > root.val) {
            //右树中插入
            root.right = add(root.right, val);
        }
        return root;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        generateBSTString(root, 0, sb);
        return sb.toString();
    }

    /**
     * 先序遍历以root为根的BST，将节点值存储在sb中
     *
     * @param root
     * @param height
     * @param sb
     */
    private void generateBSTString(TreeNode root, int height, StringBuilder sb) {
        if (root == null) {
            sb.append(generateHrightStr(height)).append("NULL\n");
            return;
        }
        sb.append(generateHrightStr(height)).append(root.val).append("\n");
        generateBSTString(root.left, height + 1, sb);
        generateBSTString(root.right, height + 1, sb);
    }

    /**
     * 按照当前所处的树的层次打印 --
     * 每多一层，就多两个--
     *
     * @param height
     * @return
     */
    private String generateHrightStr(int height) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < height; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
}
